package com.gxgeek.algorithm.t2;

import java.util.Scanner;

/**
 * Created by gx on 2017/5/5.
 */
class DATA2 {
    String key;  				//结点的关键字
    String name;
    int age;
}
class CLType{
    DATA2 nodeData = new DATA2();
    CLType nextNode;

    CLType CLAaddEnd(CLType head,DATA2 nodeData){
        CLType node, htemp;
        if ((node=new CLType())==null){
            System.out.println("申请内存失败");
            return null;
        }else {//分配内存

            node.nodeData = nodeData;
            node.nextNode = null;
            if (head==null){
                head=node;
                return head;
            }

            htemp= head;
            while (htemp.nextNode!=null){  //增加节点
                htemp=htemp.nextNode;
            }
            htemp.nextNode=node;
            return head;
        }

    }


    CLType CLaddFirst(CLType head,DATA2 nodeData){
        CLType node;
        if ((node=new CLType())==null){
            System.out.println("申请内存失效");
            return null;
        }else {
            node.nodeData = nodeData;
            node.nextNode = head;
            head = node;
            return node;
        }
    }

    //查找节点
    CLType CLFindNode(CLType head,String key){
        CLType htemp;
        htemp= head;
        while (htemp!=null){
            if (htemp.nodeData.key.compareTo(key) ==0){
                return htemp;
            }
            htemp=htemp.nextNode;
        }
        return null;
    }


    //插入结点
    CLType ClinsertNode(CLType head,String findkey,DATA2 data2){
        CLType node,nodetemp;
        if ((node = new CLType())==null){
            System.out.println("申请内存失效");
            return null;
        }

        node.nodeData = data2;
        nodetemp = CLFindNode(head,findkey);
        if (nodetemp!=null){  //找到插入点
            node.nextNode=nodetemp.nextNode;  //新插入点指向 关键节点的下一个节点
            nodetemp.nextNode=node;    //设置关键节点指向新插入节点
        }else {
            System.out.println("未找到插入节点");
        }
        return head;
    }



    //删除节点
    int CLDeleteNode(CLType head,String key){
        CLType node,htemp;

        htemp = head;

        node = head;

        while (htemp!=null){
            //找到关键字
            if (htemp.nodeData.key.compareTo(key) ==0){
                node.nextNode = htemp.nextNode;
                htemp = null;
                return 1;
            }else {//没找到指向下一个节点
                node = htemp ;
                htemp = htemp.nextNode;
            }
        }
        return 0;
    }


    int CLLength(CLType head){
        CLType htemp;
        int Len =0;
        htemp = head;

        while (htemp!=null){
            Len++;
            htemp=htemp.nextNode;
        }
        return Len;
    }

    void CLAllNode(CLType head){
        CLType htemp;
        DATA2 nodeData;
        htemp=head;
        System.out.printf("当前链表共有%d个结点。链表所有数据如下：\n",CLLength(head));
        while(htemp!=null){ 								//循环处理链表每个结点
            nodeData=htemp.nodeData;				//获取结点数据
            System.out.printf("结点(%s,%s,%d)\n",nodeData.key,nodeData.name,nodeData.age);
            htemp=htemp.nextNode;					//处理下一结点
        }

    }
}



public class Linked_List {
    private Linked_List() {
    }

    public static void main(String[] args) {
        CLType node, head=null;
        CLType CL=new CLType();
        String key,findkey;
        Scanner input=new Scanner(System.in);

        System.out.print("链表测试。先输入链表中的数据，格式为：关键字 姓名 年龄\n");
        do
        {
            DATA2 nodeData=new DATA2();
            nodeData.key=input.next();
            if(nodeData.key.equals("0"))
            {
                break; //若输入0，则退出
            }
            else
            {
                nodeData.name=input.next();
                nodeData.age=input.nextInt();
                head=CL.CLAaddEnd(head,nodeData);//在链表尾部添加结点
            }
        }while(true);
        CL.CLAllNode(head); 							//显示所有结点

        System.out.printf("\n演示插入结点，输入插入位置的关键字：") ;
        findkey=input.next();  						//输入插入位置关键字
        System.out.print("输入插入结点的数据(关键字 姓名 年龄):");
        DATA2 nodeData=new DATA2();
        nodeData.key=input.next();
        nodeData.name=input.next();
        nodeData.age=input.nextInt();//输入插入结点数据
        head=CL.ClinsertNode(head,findkey,nodeData);		//调用插入函数
        CL.CLAllNode(head); 							//显示所有结点

        System.out.print("\n演示删除结点，输入要删除的关键字:");

        key=input.next();								//输入删除结点关键字
        CL.CLDeleteNode(head,key); 					//调用删除结点函数
        CL.CLAllNode(head); 							//显示所有结点

        System.out.printf("\n演示在链表中查找，输入查找关键字:");
        key=input.next();							//输入查找关键字
        node=CL.CLFindNode(head,key);					//调用查找函数，返回结点指针
        if(node!=null)									//若返回结点指针有效
        {
            nodeData=node.nodeData;				//获取结点的数据
            System.out.printf("关键字%s对应的结点为(%s,%s,%d)\n" ,key,nodeData.key,nodeData.name,nodeData.age);
        }
        else										//若结点指针无效
        {
            System.out.printf("在链表中未找到关键字为%s的结点！\n",key);
        }

    }


}
